Delphine Boucher

IRMAR, University of Rennes

Introduction: Skew polynomials.

In this talk we will see how to build families of codes by using the ring of skew polynomials. I will focus particularly on families of codes that generalize well known families of codes for which efficient decoding algorithms exist such as cyclic Reed-Solomon codes or generalized Reed-Solomon codes. I will also explain a way of generalizing the Hamming metric to the skew polynomial setting by considering the skew metric.

Research: Decoding skew codes.

In this talk I will focus on decoding algorithms for skew codes in the Hamming and in the skew metric, especially the decoding of generalized skew Reed-Solomon codes and of skew cyclic skew Reed-Solomon codes. We will see the limits of the skew metric and will give some open questions if time permits.

Julien Lavauzelle

LAGA, University Paris 8

Decoding codes with locality.

Due to their historical applications in communication, standard decoding algorithms take as input an entire noisy codeword and aim to output the (list of) codeword(s) that is (are) closest to this noisy codeword. In this context, we usually want to design codes that can correct as many errors as possible, in polynomial time.
However, recent applications (e.g. in distributed storage) have required new contraints on codes. For instance, to cope with server failures efficiently, we need to recover pieces of any codeword in time and space that are sublinear in the message length. Depending on practical contexts and goals (low-bandwidth recovery, confidentiality, etc.), so-called regenerating codes, locally recoverable codes or locally decodable codes were thus designed.
In the first talk, we will provide a broad overview of these families of codes with locality, including bounds on their parameters, optimal constructions and decoding techniques that are specific to this context. In the second talk, we will examine the global properties of some of these codes (including Reed-Muller codes and variants), notably concerning their construction and decodability. If time permits, we will also discuss possible applications and extensions of codes with locality to information security.

Slides

Ilaria Zappatore

XLIM, University of Limoges

Algebraic code decoding in Hamming and Rank metrics: to unicity and beyond.

Algebraic codes over finite fields play a central role in both theory and applications. Two major families are Reed-Solomon codes, endowed with the Hamming metric, and Gabidulin codes, with the rank metric. In both cases, decoding can be formulated through the rational function reconstruction problem. Classical approaches, such as syndrome-based decoding (via the Berlekamp–Massey Algorithm) and interpolation-based methods (the Welch–Berlekamp approach via the Extended Euclidean Algorithm), succeed up to the unique decoding radius. Over the years, several techniques have been developed to go beyond this bound for Reed-Solomon codes (interleaving, power decoding, list decoding up to the Johnson radius, …). For Gabidulin codes, however, the landscape is quite different: while interleaving is still possible, list decoding beyond the unique decoding radius is provably impossible, and no analogue of power decoding is known.
The aim of this talk is to present a unified framework for these results, explore the parallels and contrasts between the two metrics, and discuss recent contributions in this field.

Slides: talk 1 and talk 2